/* ****************************************************************************
 *
 * Copyright (c) Microsoft Corporation. 
 *
 * This source code is subject to terms and conditions of the Microsoft Public License. A 
 * copy of the license can be found in the License.html file at the root of this distribution. If 
 * you cannot locate the  Microsoft Public License, please send an email to 
 * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound 
 * by the terms of the Microsoft Public License.
 *
 * You must not remove this notice, or any other, from this software.
 *
 * THIS CODE AND INFORMATION ARE PROVIDED "AS IS" WITHOUT WARRANTY OF ANY
 * KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A
 * PARTICULAR PURPOSE.
 * ***************************************************************************/


#if !defined(AFX_LISTCONTOUR_H__84C3BBC0_6F70_416A_8194_9657813FF3AE__INCLUDED_)
#define AFX_LISTCONTOUR_H__84C3BBC0_6F70_416A_8194_9657813FF3AE__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "Contour.h"

namespace contour
{

/*! \brief A contour class that generates line strip

\ingroup ContourLibGroup
*/
template<class T>
class TListContour : public TContour<T>  
{
public:
	//! A list of vertices index.
	typedef std::list<int> LineStrip;
	//! A list of CLineStrip.
	typedef std::list<LineStrip*> LineStripList;
	//! \name Constructors
	//@{
	TListContour():m_pStripLists(NULL){};
	virtual ~TListContour(){CleanMemory();};
	//@}

	//! \name Main methods
	//@{
	//! Initializing memory
	virtual void InitMemory();
	//! Cleaning memory and line strips
	virtual void CleanMemory();
	//! Generate contour strips
	virtual void Generate();
	//@}


	//! \name Line strip manipulation
	//@{
	//! retreiving list of line strip for the i-th contour
	LineStripList* GetLines(UINT iPlane)	{	_ASSERT(iPlane>=0); _ASSERT(iPlane<m_vPlanes.size());		return &m_pStripLists[iPlane];};
	//! Basic algorithm to concatanate line strip. Not optimized at all !
	void CompactStrips();
	//@}

protected:
	
	//! Adding segment to line strips
	virtual void ExportLine(UINT iPlane,int x1, int y1, int x2, int y2);
	//! Merges pStrip1 with pStrip2 if they have a common end point
	bool MergeStrips(LineStrip* pStrip1, LineStrip* pStrip2);

	//! \name Attributes
	//@{
	//! array of line strips
	LineStripList* m_pStripLists;
	//@}
};

template<class T>
void TListContour<T>::Generate()
{
	// generate line strips
	TContour<T>::Generate();
	// compact strips
	CompactStrips();
}

template<class T>
void TListContour<T>::InitMemory()
{
	TContour<T>::InitMemory();

	LineStripList::iterator pos;
	LineStrip* pStrip;

	if (m_pStripLists)
	{
		UINT i;
		// reseting lists
		for (i=0;i<m_vPlanes.size();i++)
		{
			for (pos = m_pStripLists[i].begin(); pos!=m_pStripLists[i].end() ; pos++)
			{
				pStrip=(*pos);
				ASSERT(pStrip);
				pStrip->clear();
				delete pStrip;
			}
			m_pStripLists[i].clear();
		}
	}
	else
		m_pStripLists=new LineStripList[m_vPlanes.size()];
}

template<class T>
void TListContour<T>::CleanMemory()
{
	TContour<T>::CleanMemory();

	LineStripList::iterator pos;
	LineStrip* pStrip;
	if (m_pStripLists)
	{
		UINT i;
		// reseting lists
		for (i=0;i<m_vPlanes.size();i++)
		{
			for (pos=m_pStripLists[i].begin(); pos!=m_pStripLists[i].end();pos++)
			{
				pStrip=(*pos);
				ASSERT(pStrip);
				pStrip->clear();
				delete pStrip;
			}
			m_pStripLists[i].clear();
		}
		delete[] m_pStripLists;
		m_pStripLists=NULL;
	}
}

template<class T>
void TListContour<T>::ExportLine(UINT iPlane,int x1, int y1, int x2, int y2)
{
	ASSERT(iPlane>=0);
	ASSERT(iPlane<m_vPlanes.size());

	// check that the two points are not at the beginning or end of the  some line strip
	int i1=y1*(m_iColSec+1)+x1;
	int i2=y2*(m_iColSec+1)+x2;

	LineStrip* pStrip;

	LineStripList::iterator pos;
	for(pos=m_pStripLists[iPlane].begin(); pos!=m_pStripLists[iPlane].end(); pos++)
	{
		pStrip=(*pos);
		ASSERT(pStrip);
		// check if points are appendable to this strip
		if (i1==pStrip->front())
		{
			pStrip->insert(pStrip->begin(),i2);
			return;
		}
		if (i1==pStrip->back())
		{
			pStrip->insert(pStrip->end(),i2);
			return;
		}
		if (i2==pStrip->front())
		{
			pStrip->insert(pStrip->begin(),i1);
			return;
		}
		if (i2==pStrip->back())
		{
			pStrip->insert(pStrip->end(),i1);
			return;
		}
	}

	// segment was not part of any line strip, creating new one
	pStrip=new LineStrip;
	pStrip->insert(pStrip->begin(),i1);
	pStrip->insert(pStrip->end(),i2);
	m_pStripLists[iPlane].insert(m_pStripLists[iPlane].begin(),pStrip);
}

template<class T>
bool TListContour<T>::MergeStrips(LineStrip* pStrip1, LineStrip* pStrip2)
{
	LineStrip::iterator pos;
	LineStrip::reverse_iterator rpos;
	if (pStrip2->empty())
		return false;

	int index;
	// debugging stuff
	if (pStrip2->front()==pStrip1->front())
	{
		// retreiving first element
		pStrip2->pop_front();
		// adding the rest to strip1
		for (pos=pStrip2->begin(); pos!=pStrip2->end();pos++)
		{
			index=(*pos);
			ASSERT(index>=0);
			pStrip1->insert(pStrip1->begin(),index);
		}
		pStrip2->clear();
		return true;
	}

	if (pStrip2->front()==pStrip1->back())
	{
		pStrip2->pop_front();
		// adding the rest to strip1
		for (pos=pStrip2->begin(); pos!=pStrip2->end();pos++)
		{
			index=(*pos);
			ASSERT(index>=0);
			pStrip1->insert(pStrip1->end(),index);
		}
		pStrip2->clear();
		return true;
	}

	if (pStrip2->back()==pStrip1->front())
	{
		pStrip2->pop_back();
		// adding the rest to strip1
		for (rpos=pStrip2->rbegin(); rpos!=pStrip2->rend();rpos++)
		{
			index=(*rpos);
			ASSERT(index>=0);
			pStrip1->insert(pStrip1->begin(),index);
		}
		pStrip2->clear();
		return true;
	}

	if (pStrip2->back()==pStrip1->back())
	{
		pStrip2->pop_back();
		// adding the rest to strip1
		for (rpos=pStrip2->rbegin(); rpos!=pStrip2->rend();rpos++)
		{
			index=(*rpos);
			ASSERT(index>=0);
			pStrip1->insert(pStrip1->end(),index);
		}
		pStrip2->clear();
		return true;
	}

	return false;
}

template<class T>
void TListContour<T>::CompactStrips()
{
	LineStrip* pStrip;
	LineStrip* pStripBase;
	UINT i;
	LineStripList::iterator pos,pos2;
	LineStripList newList;
	bool again, changed;	

	for (i=0;i<m_vPlanes.size();i++)
	{
		again=true;
		while(again)
		{
			again=false;
			// building compacted list
			ASSERT(newList.empty());
			for (pos=m_pStripLists[i].begin(); pos!=m_pStripLists[i].end();pos++)
			{
				pStrip=(*pos);
				for (pos2=newList.begin(); pos2!=newList.end();pos2++)
				{
					pStripBase=(*pos2);
					changed=MergeStrips(pStripBase,pStrip);
					if (changed)
						again=true;
					if (pStrip->empty())
						break;
				}
				if (pStrip->empty())
					delete pStrip;
				else
					newList.insert(newList.begin(),pStrip);
			}

			// deleting old list
			m_pStripLists[i].clear();
			// Copying all
			for (pos2=newList.begin(); pos2 != newList.end(); pos2++)
			{
				pStrip=(*pos2);
				if (!(pStrip->front()==pStrip->back() && pStrip->size()==2))
					m_pStripLists[i].insert(m_pStripLists[i].begin(),pStrip );
				else 
					delete pStrip;
			}
			// emptying temp list
			newList.clear();
		}
	}
}


};

#endif // !defined(AFX_LISTCONTOUR_H__84C3BBC0_6F70_416A_8194_9657813FF3AE__INCLUDED_)
